package 剑指offer;

public class _53在排序数组中查找数字 {
	/**
	 * 
	 *@time 2021年3月21日上午8:51:17
	 * 
	 *@param nums
	 *@param target
	 *@return int
	 *
	 *@see 方法1 直接找
	 */
    public int search(int[] nums, int target) {
        int count = 0;
        for (int i=0; i< nums.length; i++ ){
            if(nums[i]==target) count++;
        }
    return count;
    }
    
    public int search1(int[] nums, int target) {
    	//找到的都是该数的右边一位如[1,2,3,4]找4,则返回的是 i=4,找 3 返回 3
    	return binarySearch(nums, target)-binarySearch(nums, target-1);
    }
    /**
     * 
     *@time 2021年3月21日上午9:09:24
     * 
     *@param nums
     *@param target
     *@return int
     *
     *@see 二分查找 找到的是该数的右边一位
     */
    public int binarySearch(int[] nums, int target) {
    	int i = 0 ,j = nums.length-1;
    	while(i <= j) {
    		int mid = (i+j)/2;
    		if(nums[mid] <= target ) i = mid+1;
    		else  j = mid-1;				
    	}
    	return i;
    }
}
